package com.captain.leetcode.二叉树;

import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;

/**
 * Des:
 * 给定一个 N 叉树，找到其最大深度。
 * <p>
 * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
 * <p>
 * N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：root = [1,null,3,2,4,null,5,6]
 * 输出：3
 * <p>
 * 求解 : BFS求解
 *
 * @author XL
 * @Date 2021/7/28 13:02
 */
public class N叉树的最大深度559 {

    //广度优先搜索处理
    public int maxDepth(Node root) {
        if (root == null) return 0;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int dept = 0;

        while (!queue.isEmpty()) {
            dept++;
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                Node node = queue.poll();
                List<Node> children = node.children;
                if (Objects.nonNull(children)) {
                    for (Node child : children) {
                        queue.offer(child);
                    }
                }
            }
        }
        return dept;
    }
}
